import java.util.Arrays;

public class 最低票价 {
    /**
     * https://leetcode.cn/problems/minimum-cost-for-tickets/submissions/599685055/
     * 由递归到记忆化搜索到动态规划
     */

    //纯纯递归超时版
    public static int[] arr = {1,7,30};//三个票价的天数
    public int mincostTickets(int[] days, int[] costs) {
        return dfs(days,costs,0);
    }
    public static int dfs(int[] days, int[] costs,int pos){
        //越界返回0, 已经没有可以旅行的了
        if(pos == days.length){
            return 0;
        }
        int ret = Integer.MAX_VALUE;//比较三次最小花费
        for(int i = 0;i < 3;i++){
            int j = pos;//判断票价能使用几天
            while(j < days.length && days[pos] + arr[i] > days[j]){
                j++;
            }
            //进行对比,并递归
            ret = Math.min(dfs(days,costs,j) + costs[i],ret);
        }
        return ret;

    }
    //加上记忆化搜索减少时间
    public int mincostTickets1(int[] days, int[] costs) {
        int[] dp = new int[days.length];
        Arrays.fill(dp,-1);
        return dfs(days,costs,0,dp);
    }
    public static int dfs1(int[] days, int[] costs,int pos,int[] dp){
        if(pos == days.length){
            return 0;
        }
        if(dp[pos] != -1){
            return dp[pos];
        }
        int ret = Integer.MAX_VALUE;
        for(int i = 0;i < 3;i++){
            int j = pos;
            while(j < days.length && days[pos] + arr[i] > days[j]){
                j++;
            }
            ret = Math.min(dfs(days,costs,j,dp) + costs[i],ret);
        }
        dp[pos] = ret;
        return ret;
    }
    //从后往前的动态规划
    public int mincostTickets3(int[] days, int[] costs) {
        int n = days.length;
        int[] dp = new int[n + 1];
        //除了第一个位置改成0,其余位置用最大值
        Arrays.fill(dp,0x3f3f3f3f);
        dp[n] = 0;//这一天不需要出门噢
        //从后往前遍历,其他照搬递归的
        for(int i = days.length - 1;i >= 0;i--){
            for(int k = 0;k < 3;k++){
                int j = i;
                while(j < days.length && days[i] + arr[k] > days[j]){
                    j++;
                }
                dp[i] = Math.min(dp[j] + costs[k],dp[i]);
            }
        }
        return dp[0];
    }

}
